#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define rep(i, x, y) for(int i = (x); i <= (y); ++i)
#define per(i, x, y) for(int i = (x); i >= (y); --i)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

class istream{
    char buf[13000003],*s;
    public:
        inline istream(){
#ifndef ONLINE_JUDGE
            freopen("1.in","r",stdin); freopen("P5046.out", "w", stdout);
#endif
            buf[fread(s=buf,1,13000001,stdin)]='\n';
        }
        template<typename T>
        inline void operator>>(T&rhs){
            for(rhs=0;!isdigit(*s);++s);
            while(isdigit(*s))rhs=rhs*10+(*s++&15);
        }
}in;

struct ostream{
    char buf[8000005],*s;
    inline ostream(){s=buf;}
    inline void operator<<(long long d){
        if(!d){
            *s++='0';
        }else{
            static long long w;
            for(w=1;w<=d;w*=10);
            for(;w/=10;d%=w)*s++=d/w^'0';
        }
        *s++='\n';
    }
    inline ostream&operator<<(const char&c){*s++=c;return*this;}
    inline~ostream(){fwrite(buf,1,s-buf,stdout);}
}out;


template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 1e5 + 10;
const int B = 350;
const int T = N / B + 10;

int n, m, tr[N], bel[N], xl[N], xr[N], a[N], b[N], ta[N], tb[N], f[N][T], pre[N], suf[N];
ll bf[T][T];

void add(int x, int v) { for(; x <= n; x += x & -x) tr[x] += v; }
int query(int x) { int res = 0; for(; x; x ^= x & -x) res += tr[x]; return res; }
void clr(int x) { for(; x <= n; x += x & -x) tr[x] = 0; }

int x[N], y[N], tx, ty;

int calc() {
	ll res = 0; int p = 1;
	rep(i, 1, ty) {
		while(p <= tx && x[p] <= y[i]) p++;
		res += tx - (p - 1);
	} return res;
}

ll query(const int &l, const int &r) {
	const int bl = bel[l], br = bel[r]; ll ans = 0;
	if(bl == br) {
		ans = pre[r] - (l == xl[bl] ? 0 : pre[l - 1]);
		tx = ty = 0; rep(i, xl[bl], xr[bl]) if(tb[i] < l) x[++tx] = ta[i]; else if(tb[i] >= l && tb[i] <= r) y[++ty] = ta[i];
		ans -= calc();
		return ans;
	}
	ans = suf[l] + pre[r] + bf[bl + 1][br - 1];// 散块内部贡献、整块间的贡献
	tx = ty = 0;
	rep(i, xl[bl], xr[bl]) if(tb[i] >= l) x[++tx] = ta[i];
	rep(i, xl[br], xr[br]) if(tb[i] <= r) y[++ty] = ta[i];
	ans += calc(); // 两个散块之间贡献
	int R = xr[bl], L = xl[br];
	int *f1 = f[R], *f2 = f[l - 1], *f3 = f[r], *f4 = f[L - 1];
	rep(i, bl + 1, br - 1) ans += f1[i] - f2[i] + f3[i] - f4[i]; // 整块与散块之间贡献
	return ans;
}

int main() {
	in >> n, in >> m;
	rep(i, 1, n) in >> a[i], b[i] = i, bel[i] = (i - 1) / B + 1, xr[bel[i]] = i;
	rep(i, 1, bel[n]) {
		xl[i] = xr[i - 1] + 1;
		sort(b + xl[i], b + xr[i] + 1, [&](const auto &x, const auto &y) { return a[x] < a[y]; });
		rep(j, xl[i], xr[i]) ta[j] = a[b[j]], tb[j] = b[j];
		ll cur = 0;
		rep(j, xl[i], xr[i]) { cur += query(n) - query(a[j]); add(a[j], 1); pre[j] = cur; }
		rep(j, xl[i], xr[i]) { suf[j] = cur; add(a[j], -1); cur -= query(a[j]); }
		bf[i][i] = pre[xr[i]]; rep(j, xl[i], xr[i]) clr(a[j]);
	}
	sort(b + 1, b + n + 1, [&](const auto &x, const auto &y) { return a[x] < a[y]; });
	rep(i, 1, bel[n]) {
		int p = xl[i];
		rep(j, 1, n) {
			while(p <= xr[i] && ta[p] <= a[b[j]]) p++;
			f[b[j]][i] = b[j] < xl[i] ? p - xl[i] : xr[i] - p + 1;
		}
		rep(j, 1, n) f[j][i] += f[j - 1][i];
	}
	per(i, bel[n], 1) rep(j, i + 1, bel[n]) bf[i][j] = bf[i + 1][j] + bf[i][j - 1] - bf[i + 1][j - 1] + f[xr[j]][i] - f[xl[j] - 1][i];
	ll ans = 0; 
	while(m--) {
		ll l, r; in >> l; in >> r; l ^= ans; r ^= ans;
		ans = (query(l, r)); out << ans;
	}
	return 0;
}
